﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Algorithm.Struct
{
    public class RedBlackTreeExtend<T> :RedBlackTree<T> where T : IComparable<T>, IEquatable<T>
    {
        public RedBlackTreeExtend(RedBlackTreeNodeExtend<T> node)
            : base(node)
        { }

        public RedBlackTreeNodeExtend<T> OS_Select(int i)
        {
            if (null != this.Root)
            {
                return (this.Root as RedBlackTreeNodeExtend<T>).OS_Select(i);
            }
            return null;
        }

        public int OS_Rank(RedBlackTreeNodeExtend<T> xNode)
        {
            if (null != this.Root)
            {
                return (this.Root as RedBlackTreeNodeExtend<T>).OS_Rank(xNode);
            }
            return 0;
        }

        public override void RBInsert(RedBlackTreeNode<T> node)
        {
            node.Tree = this;
            if (null == this.Root)
            {
                node.Color = NodeColor.Black;
                this.Root = node;
            }
            else
            {
                TreeNode<T> nodeParent = null;
                var tmp = this.Root;
                while (EmptyTreeNode<T>.Instance() != tmp)
                {
                    nodeParent = tmp;
                    if (node.Data.CompareTo(tmp.Data) < 0)
                    {
                        tmp = tmp.LeftNode;
                    }
                    else
                    {
                        tmp = tmp.RightNode;
                    }
                }
                node.Parent = nodeParent;
                if (EmptyTreeNode<T>.Instance() == nodeParent)
                {
                    this.Root = node;
                }
                else if (node.Data.CompareTo(nodeParent.Data) < 0)
                {
                    nodeParent.LeftNode = node;
                }
                else
                {
                    nodeParent.RightNode = node;
                }
                node.Color = NodeColor.Red;

                var parent = nodeParent as RedBlackTreeNodeExtend<T>;
                while (EmptyTreeNode<T>.Instance() != parent)
                {
                    parent.Size = parent.Size + 1;
                    parent = parent.Parent as RedBlackTreeNodeExtend<T>;
                }

                RB_Insert_Fixup(node as RedBlackTreeNodeExtend<T>);
            }
        }

        public override void RB_Delete(RedBlackTreeNode<T> node)
        {
            TreeNode<T> willDel = null;
            if (EmptyTreeNode<T>.Instance() == node.LeftNode || EmptyTreeNode<T>.Instance() == node.RightNode)
            {
                willDel = node;
            }
            else
            {
                willDel = node.GetSuccessor();
            }

            TreeNode<T> willDelChild = null;
            if (EmptyTreeNode<T>.Instance() != willDel.LeftNode)
            {
                willDelChild = willDel.LeftNode;
            }
            else
            {
                willDelChild = willDel.RightNode;
            }

            //更新原孙子节点父指针指向
            willDelChild.Parent = willDel.Parent;

            //更新尺寸
            var parent = willDel.Parent as RedBlackTreeNodeExtend<T>;
            while (EmptyTreeNode<T>.Instance() != parent)
            {
                parent.Size = parent.Size - 1;
                parent = parent.Parent as RedBlackTreeNodeExtend<T>;
            }

            //如果被删除的是根节点
            if (EmptyTreeNode<T>.Instance() == willDel.Parent)
            {
                this.Root = willDelChild;
            }
            else if (willDel == willDel.Parent.LeftNode) //更新原祖父节点的孩子指针
            {
                willDel.Parent.LeftNode = willDelChild;
            }
            else
            {
                willDel.Parent.RightNode = willDelChild;//更新原祖父节点的孩子指针
            }

            //下面的判断说明willDel 节点为后继节点
            if (willDel != node)
            {
                node.Data = willDel.Data;
            }

            var del = willDel as RedBlackTreeNode<T>;
            if (del.Color == NodeColor.Black)
            {
                RB_Delete_Fixup(willDelChild as RedBlackTreeNodeExtend<T>);
            }
        }
    }

    public class RedBlackTreeNodeExtend<T> : RedBlackTreeNode<T> where T : IComparable<T>
    {
        public RedBlackTreeNodeExtend(T data):base(data)
        {
            this.Size = 1;
        }

        public RedBlackTreeNodeExtend()
            : base()
        {
            this.Size = 1;
        }

        public int Size
        {
            get;
            set;
        }

        public RedBlackTreeNodeExtend<T> OS_Select(int i)
        {
            var r = (this.LeftNode as RedBlackTreeNodeExtend<T>).Size + 1;
            if (r == i)
            {
                return this;
            }
            else if (i < r)
            {
                if (EmptyTreeNode<T>.Instance() != this.LeftNode)
                {
                    return (this.LeftNode as RedBlackTreeNodeExtend<T>).OS_Select(i);
                }
                else
                {
                    return null;
                }
            }
            else
            {
                if (EmptyTreeNode<T>.Instance() != this.RightNode)
                {
                    return (this.RightNode as RedBlackTreeNodeExtend<T>).OS_Select(i - r);
                }
                else
                {
                    return null;
                }
            }
        }

        public int OS_Rank(RedBlackTreeNodeExtend<T> xNode)
        {
            var r = (xNode.LeftNode as RedBlackTreeNodeExtend<T>).Size + 1;
            var current = xNode;
            while (current != xNode.Tree.Root)
            {
                if (current == xNode.Parent.RightNode)
                {
                    r = r + (xNode.Parent.LeftNode as RedBlackTreeNodeExtend<T>).Size + 1;
                }
                current = current.Parent as RedBlackTreeNodeExtend<T>;
            }

            return r;
        }

        /// <summary>
        /// 左旋说明：左旋某个非空节点x，首先假设该节点的右孩子非空，然后让它的右孩子 y代替该节点的位置，该节点x连接到原右孩子y的左孩子上，
        /// y的左孩子成为x的右孩子。
        /// </summary>
        public override void Left_Rotate()
        {
            //判断该节点右树不为空
            Debug.Assert(null != this.RightNode);

            //将该节点下面的右节点的左子树，连接到该节点右孩子
            var rightNode = this.RightNode;
            this.RightNode = rightNode.LeftNode;
            if (EmptyTreeNode<T>.Instance() != rightNode.LeftNode)
            {
                rightNode.LeftNode.Parent = this;
            }

            //更新右孩子的父指针
            rightNode.Parent = this.Parent;

            //判断是否更新树根节点
            if (EmptyTreeNode<T>.Instance() == this.Parent)
            {
                this.Tree.Root = rightNode;
            }//判断该节点为父节点的左孩子还是右孩子，更新父节点的指针
            else
            {
                if (this == this.Parent.LeftNode)
                {
                    this.Parent.LeftNode = rightNode;
                }
                else
                {
                    this.Parent.RightNode = rightNode;
                }

            }

            //将该节点移到右孩子的左节点上
            rightNode.LeftNode = this;
            this.Parent = rightNode;

            //添加更新size大小的代码
            (rightNode as RedBlackTreeNodeExtend<T>).Size = (this as RedBlackTreeNodeExtend<T>).Size;
            (this as RedBlackTreeNodeExtend<T>).Size = ((this as RedBlackTreeNodeExtend<T>).LeftNode as RedBlackTreeNodeExtend<T>).Size +
                ((this as RedBlackTreeNodeExtend<T>).RightNode as RedBlackTreeNodeExtend<T>).Size + 1;
        }

        /// <summary>
        /// 右旋是上面左旋的叛过程
        /// </summary>
        public override void Right_Rotate()
        {
            //判断该节点右树不为空
            Debug.Assert(null != this.LeftNode);

            //将该节点下面的右节点的左子树，连接到该节点右孩子
            var leftNode = this.LeftNode;
            this.LeftNode = leftNode.RightNode;
            if (EmptyTreeNode<T>.Instance() != leftNode.RightNode)
            {
                leftNode.RightNode.Parent = this;
            }

            //更新右孩子的父指针
            leftNode.Parent = this.Parent;

            //判断是否更新树根节点
            if (EmptyTreeNode<T>.Instance() == this.Parent)
            {
                this.Tree.Root = leftNode;
            }//判断该节点为父节点的左孩子还是右孩子，更新父节点的指针
            else
            {
                if (this == this.Parent.LeftNode)
                {
                    this.Parent.LeftNode = leftNode;
                }
                else
                {
                    this.Parent.RightNode = leftNode;
                }

            }

            //将该节点移到右孩子的左节点上
            leftNode.RightNode = this;
            this.Parent = leftNode;

            //添加更新size大小的代码
            (leftNode as RedBlackTreeNodeExtend<T>).Size = (this as RedBlackTreeNodeExtend<T>).Size;
            (this as RedBlackTreeNodeExtend<T>).Size = ((this as RedBlackTreeNodeExtend<T>).LeftNode as RedBlackTreeNodeExtend<T>).Size +
                ((this as RedBlackTreeNodeExtend<T>).RightNode as RedBlackTreeNodeExtend<T>).Size + 1;
        }
    }
}
